package com.itzmn.newcode.offer;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/16 14:27
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer  查找数组中最小的k个数
 *
 *  思路：
 *   先对数组进行排序，然后打印最小的
 */
public class FindNumIsMin {

    public static void main(String[] args) {

        int[] arrs = {1,3,6,7,5,2,8};
        new FindNumIsMin().GetLeastNumbers_Solution(arrs,3);

    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> integers = new ArrayList<>();
        if (k>input.length){
            return integers;
        }
        qk(input,0,input.length-1);

        for (int i=0;i<k;i++){
            integers.add(input[i]);
        }
        System.out.println(integers);
        return integers;
    }

    public void log(int arrs[]){

        for (int i=0;i<arrs.length;i++){
            System.out.print(arrs[i]+" ");
        }
        System.out.println();
    }
    //归并排序，先对数组分，然后治

    public void qk(int[] arrs,int left,int right){

        if (left<right){
            int min = (right + left) / 2;
            qk(arrs,left,min);
            qk(arrs,min+1,right);

            //合并
            sort(arrs,left,right,min);
            log(arrs);
        }


    }

    /**
     * 对两个数组进行合并
     * @param arrs 数组
     * @param left 左侧数组的开始位置
     * @param right 右侧数组的结束位置
     * @param min 左侧数组的结束位置
     */
    public void sort(int[] arrs,int left,int right,int  min){

        int[] ints = new int[right - left+1];

        int i=left;
        int j=min+1;
        int k=0;
        while (i<=min && j<=right){
            if (arrs[i]<=arrs[j]){
                ints[k++] = arrs[i++];
            }else {
                ints[k++] = arrs[j++];
            }
        }

        //如果第一个数组还有值，将数据全部加入临时数组
        while (i<=min){
            ints[k++] = arrs[i++];
        }
        while (j<=right){
            ints[k++] = arrs[j++];
        }

        // 将临时数组中的数据，重新赋值给真正的数组
        for (int k2 = 0; k2 < ints.length; k2++) {
            arrs[k2 + left] = ints[k2];
        }

    }





}
